package com.zhanghp.class034;

import com.zhanghp.common.ListNode;

/**
 * 排序链表<br/>
 * 要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性<br/>
 * 数组排序做不到，链表排序可以<br/>
 * 测试链接 : https://leetcode.cn/problems/sort-list/<br/>
 * <p>
 * 调用递归，会有额外空间复杂度O(logn)
 * <p>
 * 所以用非递归迭代
 *
 * @author zhanghp
 * @since 2024/4/11 9:56
 */
public class Code06_SortList {

    static class Solution {

        /**
         * 排序后的头
         * <p>
         * 便于迭代步长,将上一组的尾链接排序后的头
         */
        public ListNode start;
        /**
         * 排序后的尾
         * <p>
         * 便于迭代步长,设值成当前排序后的尾，方便下一组迭代使用
         */
        public ListNode end;

        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;
            return mergeStepSort(head);
        }

        // 提交如下的方法
        // 时间复杂度O(n*logn)，额外空间复杂度O(1)，有稳定性
        // 注意为了额外空间复杂度O(1)，所以不能使用递归
        // 因为mergeSort递归需要O(log n)的额外空间
        public ListNode mergeStepSort(ListNode head) {
            int n = 0;
            ListNode cur = head;
            do {
                n++;
                cur = cur.next;
            } while (cur != null);
//            int n = size(head);

            ListNode l1, l2, r1, r2, next, lastTeamEnd;
            for (int step = 1; step < n; step <<= 1) {
                // 第一组很特殊，因为要决定整个链表的头，所以单独处理
                l1 = head;
                r1 = findEnd(l1, step);
                // 这个地方不用判断l2,r2为空
                // 如果触碰边界的话
                // 1.如果l2为空，step < n直接打破循环了
                // 2.如果r2为空，findEnd通过l2（基于第一点）不会返回空
                l2 = r1.next;
                r2 = findEnd(l2, step);
                next = r2.next;
                r1.next = null;
                r2.next = null;
                merge(l1, r1, l2, r2);
                head = start;
                lastTeamEnd = end;
                while (next != null) {
                    l1 = next;
                    r1 = findEnd(l1, step);
                    l2 = r1.next;
                    // 这个地方判断的原因，触碰边界
                    // 并不会因为上面的step<n而break，因为这个属于while的循环
                    if (l2 == null) {
                        lastTeamEnd.next = l1;
                        break;
                    }
                    r2 = findEnd(l2, step);
                    next = r2.next;
                    r1.next = null;
                    r2.next = null;
                    merge(l1, r1, l2, r2);
                    lastTeamEnd.next = start;
                    lastTeamEnd = end;
                }

            }
            return head;
        }


        // l1...r1 -> null : 有序的左部分
        // l2...r2 -> null : 有序的右部分
        // 整体merge在一起，保证有序
        // 并且把全局变量start设置为整体的头，全局变量end设置为整体的尾
        public void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) {
            // 初始化pre节点
            ListNode pre;
            if (l1.val <= l2.val) {
                pre = l1;
                l1 = l1.next;
            } else {
                pre = l2;
                l2 = l2.next;
            }
            start = pre;

            // 排序
            while (l1 != null && l2 != null) {
                pre.next = l1.val <= l2.val ? l1 : l2;
                // 设值l1,l2,pre循环值
                pre = pre.next;
                if (pre == l1) {
                    l1 = l1.next;
                } else {
                    l2 = l2.next;
                }
            }

            // 收尾处理
            // r1,r2选择end赋值
            if (l1 != null) {
                pre.next = l1;
                end = r1;
            } else {
                pre.next = l2;
                end = r2;
            }
        }

        /**
         * listNode 长度
         * <p>
         * 单独写个方法调用，时间效率打败25，空间打败70
         * <p>
         * 而直接在方法内写，时间效率打败57，空间打败70
         * <p>
         * 奇怪！？同样的执行步骤，多调用个方法却多花时间
         *
         * @param node 节点
         * @return 长度
         */
        public int size(ListNode node) {
            int size = 0;
            if (node == null) return size;
            do {
                size++;
                node = node.next;
            } while (node != null);
            return size;
        }


        /**
         * 包括s在内，往下数k个节点返回<br/>
         * 如果不够，返回最后一个数到的非空节点
         *
         * @param n 节点
         * @param k 数量
         * @return 节点
         */
        public ListNode findEnd(ListNode n, int k) {
            while (n.next != null && --k > 0) {
                n = n.next;
            }
            return n;
        }

    }
}
